#ifndef STATIC_ALLOCATOR_H_INCLUDED
#define STATIC_ALLOCATOR_H_INCLUDED

/*
* Copyright (c) 2010 Michael Collins
*
* This file is part of TerraFirma.
*
* TerraFirma is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* TerraFirma is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with TerraFirma.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <vector>
#include <stack>
#include <stdint.h>
#include <stdexcept>

/** A collection of statically-typed objects that offers constant time
 * add, remove, and access. (amortized in the add case) this is meant
 * to be fast, but only works as a collection of a single type
 *
 * This is a refined model of a memory pool, but meant to be consistent across hosts
 */

/** IMPLEMENTATION NOTES:
 *  This is tricky. What we want is a variably-sized array, much like the STL container.
 *  However, we don't want to call destructors on the elements when we go through a
 *  resize operation, and we want to keep it fast. As a memory pool, this object decouples
 *  memory initialization from memory allocation, and vice versa. So we have to make clever
 *  use of malloc() and free() when resizing, and pass the allocate() member to the -new-
 *  operator so C++ can call the constructor for inserted objects and initialize them without
 *  heap fragmentation and memory allocation
 *
 *  The caveat that comes from doing this is that pointers to objects inside the container
 *  are mutable. You should not consider a pointer to any of these objects to be consistent
 *  To access elements in the pool, always ALWAYS use an index. This is cross-host consistent,
 *  after all.
 */

 //Given a base and offset pointer, determine the array index that the offset points to
 //b - base pointer, o - offset pointer, s - element size
 #define TO_ARRAY_IDX(b,o,s) (((size_t)(((const void*)(o)) - ((const void*)(b)))) / (s))

namespace engine
{
    template<typename T>
    class static_heap
    {
    private:
        struct entry
        {
            //uint32_t next_entry; //Implements a sort of linked-list
            entry(): freed(true) {} //Defaults to a null payload
            entry(const T& o): freed(false), payload(o) {}
            bool freed;
            T payload;
        };
        uint32_t size_; //Number of valid entries in the container
        //uint32_t capacity; //Number of entries that you can have *right now* without resizing the array
        std::stack<uint32_t> free_list; //collection of entries that are all empty
        //std::vector<entry> array; //Collection of allocated objects. Can hold empty objects
        entry* arr; //pointer to memory pool
        size_t capacity; //total capacity (in elements) of the allocated pool
        size_t arr_size; //how much the contiguous region (in elements) has been used (including freed spots)
        size_t eff_size; //Effective size. Number of elements initialized not including free spots

        //uint32_t front, end; //indices to the first and last initialized entries. End points to the element after the last

        //Marks an entry as initialized or free (depending on flag) without messing up data or initializing anything
        T* mark_entry(uint32_t n, bool flag)
        {
            arr[n].freed = flag;
            return &(arr[n].payload);
        }

        //Doubles the capacity of the array (pointers to elements are no longer valid after this is called)
        //Unlike STL vector resize operation, this should not call destructors!
        void grow()
        {
            size_t oldcap = capacity;
            if(capacity == 0)
                arr = (entry*) malloc(++capacity * sizeof(entry));
            else
                arr = (entry*) realloc(arr, (capacity<<=1) * sizeof(entry)); //Double the array capacity

            //Mark all new entry spaces as free
            for(; oldcap < capacity; ++oldcap)
                mark_entry(oldcap, true);
        }

        //Returns a pointer to the first initialized entry
        entry* front() const
        {
            if(empty())
                return arr;
            //entry* ptr = arr;
            for(uint32_t n = 0; n < arr_size; ++n)
            {
                if(is_valid(n))
                    return arr+n;
            }
            return arr; //Shouldn't get to this point, but whatever
        }

        //Returns a pointer to the entry after the entry with the highest index
        entry* back() const
        {
            if(empty())
                return arr;
            for(uint32_t n = arr_size; n > 0; --n)
            {
                if(is_valid(n-1))
                    return arr + n;
            }
            return arr; //Shouldn't get to this point, but whatever
        }

    public:
        //Elements are read-only, and iterator only goes over an immutable array.
        //This is really open up to race conditions. We should make an offset-based
        //iterator rather than one with absolute pointers. Only use this when you
        //know that the array will not be modified in any way.
        struct const_iterator
        {
        public:
            const_iterator(): entryptr(NULL), endptr(NULL) {}
            //const_iterator(unsigned int ix): index(ix) {}

            const T& operator* () const
            {
                //this will segfault on NULL and end iterators.
                //TODO: throw exceptions in the case of invalid memory
                return entryptr->payload;
            }
            //Prefix
            //Returns true if the iterator increment succeeded (found the next valid index)
            bool operator++()
            {
                for (;++entryptr < endptr;)
                    if (!entryptr->freed)
                        return true;
                return false; //Got to the end
            }

            //Postfix (the same as prefix for now)
            //Returns true if the iterator increment succeeded (found the next valid index)
            void operator++(int)
            {
                for (;++entryptr < endptr;)
                    if (!entryptr->freed)
                        return true;
                return false; //Got to the end
            }

            bool operator< (const const_iterator& it) const
            {
                return entryptr < it.entryptr;
            }

            bool operator> (const const_iterator& it) const
            {
                return entryptr > it.entryptr;
            }

            bool operator== (const const_iterator& it) const
            {
                return entryptr == it.entryptr;
            }

            bool operator!= (const const_iterator& it) const
            {
                return entryptr != it.entryptr;
            }

            const_iterator(const entry *beg, const entry *end) : entryptr(beg), endptr(end) {}

        private:
            const entry *entryptr;
            const entry *endptr;
            //unsigned int index;
        };

        static_heap() : arr(NULL), capacity(0), arr_size(0), eff_size(0) {}
        //Capacity constructor (cap is in number of elements)
        static_heap(uint32_t cap) : capacity(cap), arr_size(0), eff_size(0)
        {
            arr = (entry*) malloc(cap*sizeof(entry));
            //This should throw exceptions when malloc fails. Bad form, shithead.
            //Mark all entries as uninitialized
            for(unsigned int n = 0; n < cap; ++n)
                mark_entry(n, true);
        }

        ~static_heap()
        {
            //Call the destructors on all initialized entries
            for(uint32_t n = 0; n < capacity; ++n)
                if(!arr[n].freed)
                    arr[n].payload.~T(); //Explicitly destroy all initialized objects
            free(arr);
        }

        uint32_t size() const {return eff_size;}

        bool empty() const {return eff_size == 0;}

        //Accessing methods to access the content of the container
        //Does validity and range checks, unlike the array access method
        const T& at (uint32_t n) const throw (std::out_of_range)
        {
            if(n >= arr_size)
                throw std::out_of_range(); //Head off a segfault
            //This can have undefined results if the element has been freed
            return arr[n].payload;
        }
        /*T& at (uint32_t n) throw (std::out_of_range)
        {
            entry& ent = array.at(n);
            if (ent.freed)
                return T();
            else
                return ent.payload;
        }*/

        //Array accessor
        const T& operator[] (uint32_t n) const
        {
            return arr[n].payload;
        }
        T& operator[] (uint32_t n)
        {
            return arr[n].payload;
        }

        //Is valid accessor
        //returns true if the given index has a full entry in it (unfreed)
        bool is_valid(uint32_t n) const
        {
            return !arr[n].freed;
        }

        //Allocates space a new entry without initializing it. Useful for placement new operator
        //This should ONLY EVER BE CALLED by the placement new operator. Due to constructor polymorphism,
        // we can't actually make a normal method to ensure this rule
        T* allocate()
        {
            if (free_list.empty())
            {
                //No free slots, we have to append
                if(++arr_size >= capacity)
                    //We need to resize the array
                    grow();
                return mark_entry(eff_size++, false); //Mark rearmost entry as initialized and increment size
            }
            else
            {
                //We have a place that was freed before. Use it.
                uint32_t retval = free_list.top();
                free_list.pop();
                ++eff_size;
                return mark_entry(retval, false); //Mark the previously freed entry as initialized
            }
        }

        //Adds a new object to the collection and returns the index
        //T must have an empty argument constructor in public resolution(i.e. STL compliant)
        uint32_t add()
        {
            uint32_t retval = next_idx();
            new (allocate()) T;
            return retval;
        }
        //Adds a new object to the collection and returns the index
        //T must have a copy constructor defined in public resolution (i.e. STL compliant)
        //WARNING: not thread-safe
        uint32_t add(const T& obj)
        {
            uint32_t retval = next_idx();
            new (allocate()) T(obj); //Placement new operator on a prealocated buffer
            return retval;
        }

        //Removes the entry given by the valid id
        void remove(uint32_t n)
        {
            if (!(arr[n].freed))
            {
                arr[n].freed = true;
                free_list.push(n);
                --eff_size;
                arr[n].payload.~T(); //invoke destructor w/o deallocating memory
            }
        }

        /*--add_at and remove_at are mostly for clients who aren't in control of where
            stuff is added to. (the server tells them where to add an element) In these cases,
            we don't really need to do anything with the free list, so remove it for memory's sake
        */
        //Adds a new object (potentially overwriting an old one) at the specified index
        //Never mix calls with add() and add_at(). Each host should only ever call one or the other
        uint32_t add_at(const T& obj, uint32_t n)
        {
            //Make sure the array is big enough to hold the shit
            while (n >= capacity)
                grow();
            if(n >= arr_size)
                arr_size = n+1; //Make sure arr_size grows to the right value
            if (!arr[n].freed)
            {
                //Explicitly call the destructor of an object already at this address
                arr[n].payload.~T();
            }
            else
                ++eff_size;
            arr[n].freed = false;
            new(&(arr[n].payload)) T(obj); //Call copy constructor
            return n;
        }

        void remove_at(uint32_t n)
        {
            if (!(arr[n].freed))
            {
                arr[n].freed = true;
                //free_list.push(n);
                --eff_size;
                arr[n].payload->~T(); //invoke destructor w/o deallocating memory
            }
        }

        //Returns the index of the next-useable slot
        uint32_t next_idx() const
        {
            if (free_list.empty())
                return arr_size;
            else
                return free_list.top();
        }

        const const_iterator begin() const
        {
            return const_iterator(front(), end());
        }

        const const_iterator end() const
        {
            return const_iterator(end(), end());
        }
    };
}


#endif // STATIC_ALLOCATOR_H_INCLUDED
